Graphics processing involves a performance of rapid mathematical calculations for image rendering. Such graphics workloads may be performed at a graphics processing unit (GPU), which is a specialized electronic circuit, to rapidly manipulate and alter memory to accelerate the creation of images in a frame buffer intended for output to a display. Often a GPU may be implemented to perform global optimizations. An exemplary global optimization implementation includes a graph-cut algorithm that solves a maximum flow, minimum cut problem. Graph-cut has been widely used in the computer vision field (e.g., for background segmentation, image restoration, and stereo matching, etc.).
One such graph-cut algorithm is Push and Relabel, designed by Andrew V. Goldberg and Robert Tarjan. In a Push operation, flows of each pixel are transmitted to neighboring pixels. Such flows are not a problem in applications in which a GPU is running single thread sequential operations. However, these dependencies may cause race conditions if multiple threads are running simultaneously on a GPU. For instance, to run push operations in parallel on a GPU, dependencies among neighboring pixels need to be defined in order to avoid race conditions of pixels being simultaneously referenced and updated by different threads. Such dependencies limit execution performance due to limited active threads per row or per column.